package com.sise.Tree;

import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 *      113. 路径总和 II
 *
 *      给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
 *      叶子节点 是指没有子节点的节点。
 */
public class _113_pathSum {

    List<List<Integer>> lists = new LinkedList<>();     // 保存结果集
    Deque<Integer> path = new LinkedList<>();           // 每一次的路径

    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        dfs(root, targetSum);
        return lists;
    }

    public void dfs(TreeNode root, int targetSum){
        if (root == null) return;

        path.offerLast(root.val);
        targetSum = targetSum - root.val;                                   // 这里需要相减后再赋值，不能使用 targetSum - root.val == 0，因为在后续还需要用到 targetSum 向下传递
        if (root.left == null && root.right == null && targetSum == 0){     // 如果为根节点，同时相减为 0
            lists.add(new LinkedList<>(path));
        }
        dfs(root.left, targetSum);      // 往左子树走
        dfs(root.right, targetSum);     // 往右子树走
        path.pollLast();
    }
}
